The present invention relates to digital electronic circuits, and more particularly to circuits which are capable of dividing a digital format frequency by a rational number.
A classic problem in digital circuit design has been the development of circuits which divide a succession of digital pulses of defined repetition rate or frequency by a rational number. The prevailing solutions use counters having various feedback and feedforward loops. Examples of such preexisting implementations appear in U.S. Pat. Nos. 4,295,158; 4,318,046; and 4,704,723. The first two of the noted references require hardware reconfiguration to change the divisor, while the latter provides greater latitude at the expense of increasing the number of counters, comparators, switches and registers necessary to implement even a meager division of the input frequency. Consequently, the prevailing approaches of the prior art are characteristically inflexible as to the divisor or inordinately complex as to implementation.
Digital circuits are continually being pressed for higher operating frequencies. In such context, frequency dividers that are implemented with counters consistently suffer from the ripple delays associated with multiple flip-flop stages and logic gates. Therefore, logic devices of limited complexity and elevated speed capability are clearly preferred for advanced high speed digital signal processing applications.
In applications where the divisor can be a ratio of any prime numbers greater than one, it is paritcularly important that the circuit provide on a continuous basis a accurate divided frequency in which truncations do not accumulate or become material sources of error. Therefore, a preferred circuit would provide on continuous basis the best estimate of the output frequency without truncation.
Algorithms suitable to compute the coordinates of pixels in two dimensional raster grid patterns where the end points are defined have been the subject of numerous investigations. Of particular interest is the Bresenham Line Algorithm, in that the algorithm utilizes integer arithmetic to define the pixel positions of a line in a raster grid based upon the X and Y coordinates of a starting point and an end point. The Bresenham Line Algorithm is developed and illustrated by example in the text authored by Foley et al., entitled Fundamentals of Interactive Computer Graphics, copyright 1982 by Addison-Wesley Publishing Co., as appears on pages 433-436.